題目來源:https://tioj.ck.tp.edu.tw/problems/1410
我的想法很直觀,就是用array儲存入和出的人(記得出的時間點也算,所以要加1),然後掃過去紀錄時間軸的max值。
PS:我最後發現我這樣寫不管是時間上還是空間上都很爛,所以我去看了幾位大神的寫法才發現這題可以用離散化或是用map揍掉 m(_ _)m
#pragma gcc optimize(o2)
#include<bits/stdc++.h>
#define int long long int
#define IOS ios_base::sync_with_stdio(false)
#define TO cin.tie(NULL)
using namespace std;
int str[100005];
signed main()
{
IOS;TO;
int range=0,a,b,n,maxu,ans;
while(cin >> n)
{
ans=0;maxu=0;
while(n--)
{
cin >> a >> b;
str[a]++;
b+=1;
str[b]--;
range=max(range,b);
}
for(int i=0;i<=range;i++)
{
maxu+=str[i];
ans=max(maxu,ans);
}
cout << ans <<endl;
}
return 0;
}
- 本文連結:https://blog.subarya.me/2018/12/22/[TIOJ]%201410.%20Comiket/
- 版權聲明:本Blog所有文章除了特別聲明外,均默認採用 許可之協議。